package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC767 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public String reorganizeString(String str) {
            int[] cnt = new int[26];
            for (char ch : str.toCharArray()) {
                cnt[ch - 'a']++;
            }

            Map<Integer, List<Character>> map = new TreeMap<>(Collections.reverseOrder());
            int leftCnt = str.length();
            for (int i = 0; i < 26; i++) {
                if (cnt[i] == 0) continue;
                if (null == map.get(cnt[i])) {
                    List<Character> chList = new ArrayList<>();
                    chList.add((char) ('a' + i));
                    map.put(cnt[i], chList);
                } else map.get(cnt[i]).add((char) ('a' + i));
            }

            StringBuilder sb = new StringBuilder();
            int round = 0, curRoundCount = 0, baseRoundLength = 0, curInsertPos = 0;
            for (Integer charCount : map.keySet()) {
                List<Character> characterList = map.get(charCount);
                if (round <= 0 && leftCnt - charCount < charCount - 1) return "";// 看剩余字符能否补空位,此处不能返回空字符串

                // 可以补全空位，开始循环补全
                for (Character ch : characterList) {
                    String addStr = String.valueOf(ch);
                    // 重复拼接charCount个字符
                    for (int i = 0; i < charCount; i++) {
                        sb.insert(curInsertPos, addStr);
                        curInsertPos += (round + 1);
                        if (++curRoundCount >= baseRoundLength && baseRoundLength > 0) {
                            curInsertPos = ++round;
                            curRoundCount = 0;
                        }
                    }

                    if (baseRoundLength == 0) {
                        baseRoundLength = charCount;
                        curInsertPos = ++round;
                        curRoundCount = 0;
                    }
                }
            }

            return sb.toString();
        }
    }

    public void run() {
        Solution solution = new Solution();
//        System.out.println(solution.reorganizeString("abbabbaaab"));
//        System.out.println(solution.reorganizeString("aaaabced"));
        System.out.println(solution.reorganizeString("kkkkzrkatkwpkkkktrq"));
    }

    public static void main(String[] args) throws Exception {
        LC767 an = new LC767();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
